先簡單回顧一下，今天預計分析的題目：

• 20. Valid Parentheses
  • 
• 昨天問到，如果 ([)] 是錯誤的，那什麼是正確的 ?
  • 你寫 ()[] 或 [()] 或 ([]) 都可以，在你遇到右括號時，對應的左括號，都是 same type 就可以
    • 例如 ( 對 ) 就是 same type， ( 對 ] 就不是 same type
• 在小學數學運算中，{}是大括號，[]是中括號，()是小括號，優先順序為小括號 > 中括號 > 大括號，那這一個題目，遇到 ([{}]) 這樣的情況，是不是也是可接受的 ?
  • 可以的，長大後，我們已經較少使用 [] 跟 {} 做為算式的一部分，大部分數學中的運算都是全部使用 () ，然後依照最內部的括號依序做運算
  • 中括號與大括號，在數學中有其他涵義，例如大括號常做為集合，中括號可表示高斯符號
• 根據觀察，我們是不是平常數學式中，遇到右括號，就會去找與之對應的左括號
  • 
• 所以程式整體邏輯很簡單：
  1. 我們一個個讀 s 中的每個字元，例如 s 為 {}，那我們先讀 {，再讀 }
     • PS: 這樣 { 我們會稱為字元，超過一個字元組成，就會變成字串，例如{}，會組成字串
  2. 字元遇到左括號，我們就先用 stack 盒子存起來，若字元為右括號，就把剛剛存起來的左括號拿出來比對是不是 same type
     • PS: ( 對 ) 就是 same type，( 對 ] 或 } 就不是 same type，以此類推
  3. 當每個字元都讀完，最後我們再來檢查看看 stack 是不是都空了，如果都空了，就代表他左右括號數量一樣，那就回傳 True，反之就回傳 False
     • 之所以要檢查，就是怕若 s 為 (()，那在前面兩個步驟中，stack 盒子會裝 ((，但是只遇到一次 )，只拿出一次(，所以盒子內還會有一個 (
• 不專業程式流程圖，請依照步驟慢慢對照： (菱形為判斷式；長方形為程式一般執行，可能儲存變數等..；平行四邊形為輸入與輸出；圓角長方形代表程式的開始或結束)
  • 
• 課間小Q&A：
  • 若變數 s 為 {}{}()[[]] ，stack 盒子會依序裝入哪些字元? 是否回傳 True?
    1. 曾經依序裝入 {{([[
       1. 先裝入 {，遇到 } 又把{拿出來了，所以stack 為空
       2. 再裝入 {，遇到 } 又把{拿出來了，所以stack 為空
       3. 再裝入 (，遇到 ) 又把(拿出來了，所以stack 為空
       4. 再依序裝入 [[，遇到 ] 把一個 [ 拿出來了，所以stack 裡面還有一個 [，接著又遇到 ]，又把stack 內的 [ 拿出來，此時 stack 為空
    2. 因為每次遇到右括號都是 same type，加上最後 stack 是空的，代表左右括號數量一樣，所以回傳 True
• python 一般寫法 (比較沒有彈性) ( 時間複雜度為 O(n) → 就是全部 s 長度跑一次 )

class Solution:
    def isValid(self, s: str) -> bool:
#       先宣告一個 stack 盒子，之後專門存放左括號
        stack_left = []
#       把變數 s 一個個讀字元，每一次讀的字元存在 chr 變數中
        for chr in s:
#           若 chr 為左括號
            if chr == "(" or chr == "[" or chr == "{":
                stack_left.append(chr)
#           若 chr 不是左括號  (chr 為右括號)
            else:
#               若 stack 內還有東西 (因為要拿一個 stack 盒子中的左括號，出來跟右括號比對是否為 same type)
                if stack_left:
#                   stack 盒子拿出來的左括號放在 left 變數中
                    left = stack_left.pop()
#                  接下來三個判斷式，依序判斷是否為 same type，一旦不是就直接回傳 False
                    if chr == ")" and left != "(":
                        return False
                    elif chr == "]" and left != "[":
                        return False
                    elif chr == "}" and left != "{":
                        return False
#               若都讀到右括號了，但是 stack 沒有左括號可以配對，那就直接回傳 False 
                else:
                    return False
#       判斷 stack 是否為空，stack若是空的 為 True
#       stack 內有東西
        if stack_left:
            return False
#       stack 內沒有東西了~
        else:
            return True

• 若程式想要更有彈性，可能之後不只()[]{}這幾種符號，那我們可以把比對 same type 寫成 dictionary 的結構 ( 時間複雜度為 O(n) → 就是全部 s 長度跑一次 )

class Solution:
    def isValid(self, s: str) -> bool:
        stack_left = []
        dict = {")": "(", "]": "[", "}": "{"}
        for chr in s:
#           若 chr 為 左括號
            if chr in dict.values():
                stack_left.append(chr)
#           若 chr 為 右括號
            elif chr in dict.keys():
#               若 stack 盒子是空的、沒有對應到 same type，回傳 False
                if len(stack_left) == 0 or dict[chr] != stack_left.pop():
                    return False
            else:
                return False
            
        return not stack_left